package leetcode.code337;

import java.util.HashMap;
import java.util.Map;

import leetcode.helper.tree.TreeNode;

/**
 *
 * 5%
 *
 * @author CaoYu
 * @date 2021年8月9日
 * @description
 */
public class Solution2 {

//	 Definition for a binary tree node.
	// [3,2,3,null,3,null,1]

	public int rob(TreeNode root) {
		Map<Integer, Integer> cache = new HashMap<>();
		return robNode(root, cache, 1);
	}

	public int robNode(TreeNode node, Map<Integer, Integer> cache, Integer no) {
		if (node == null)
			return 0;
		if (cache.containsKey(no)) {
			return cache.get(no);
		}
		int r1 = 0; // 包含头
		int r2 = 0; // 不包含头
		r1 = node.val + robNodeChild(node.left, cache, 2 * no) + robNodeChild(node.right, cache, 2 * no + 1);
		r2 = robNode(node.left, cache, 2 * no) + robNode(node.right, cache, 2 * no + 1);
		int max = Math.max(r1, r2);
		cache.put(no, max);
		return max;
	}

	public int robNodeChild(TreeNode node, Map<Integer, Integer> cache, Integer no) {
		if (node == null) {
			return 0;
		}
		int max = robNode(node.left, cache, 2 * no) + robNode(node.right, cache, 2 * no + 1);
		return max;
	}

}
